# 22/100 链表-相交链表
# leetcode第160题: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/25
from typing import Optional
from leetcode import test


class ListNode:
    def __init__(self, value=0):
        self.value = value
        self.next = None

    def append(self, y) -> 'ListNode':
        if type(y) is type(self.value):
            self.next = ListNode(y)
        elif type(y) is ListNode:
            self.next = y
        return self.next

    def __str__(self):
        return str(self.value)


def getIntersectionNode_bf(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    cur_a, cur_b = headA, headB
    while cur_a:
        while cur_b:
            if cur_a is cur_b:
                return cur_b
            else:
                cur_b = cur_b.next
        cur_a = cur_a.next
        cur_b = headB
    return None


def getIntersectionNode_hash(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    values_a = set()
    cur_a, cur_b = headA, headB
    while cur_a:
        values_a.add(cur_a)
        cur_a = cur_a.next

    while cur_b:
        if cur_b in values_a:
            return cur_b
        cur_b = cur_b.next
    return None


def getIntersectionNode_dbpnt(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    """快慢指针
    一个非常巧妙的方法. 当A链表走到末尾后继续从B链表的头部开始遍历, B链亦然, 直到cur_a = cur_b的时候就是交叉的节点.
    原理为:
    我们将A链表看做 X.append(Z), 其中X为A的自有部分, 其长度为x; Z为和B链表的共有部分, 其长度为z.
    那么B链表就为 Y.append(Z), Y即为B链表的自有部分, 其长度为y.
    那么我们的遍历方式遍历headA就是遍历 X.append(Z).append(Y).append(Z)
    遍历headB就是 Y.append(Z).append(X).append(Z)
    那么前面的不同部分一定为 x+y+z, 而在遍历x+y+z次之后, 一定是共有部分Z
    """
    cur_a, cur_b = headA, headB
    while cur_a != cur_b:
        cur_a = headB if not cur_a else cur_a.next
        cur_b = headA if not cur_b else cur_b.next
    return cur_b


if __name__ == '__main__':
    # 示例1
    intersect = ListNode(8)
    intersect.append(4).append(5)
    head1_a = ListNode(4)
    head1_a.append(1).append(intersect)
    head1_b = ListNode(5)
    head1_b.append(6).append(1).append(intersect)

    print(getIntersectionNode_bf(head1_a, head1_b))  # 8
    print(getIntersectionNode_hash(head1_a, head1_b))
    print(getIntersectionNode_dbpnt(head1_a, head1_b))

    # 示例2
    intersect = ListNode(2)
    intersect.append(4)
    head2_a = ListNode(1)
    head2_a.append(1).append(9).append(1).append(intersect)
    head2_b = ListNode(3)
    head2_b.append(intersect)

    print(getIntersectionNode_bf(head2_a, head2_b))  # 2
    print(getIntersectionNode_hash(head2_a, head2_b))
    print(getIntersectionNode_dbpnt(head2_a, head2_b))
